/* #define ENABLE_EVMAP_DEBUG_PRINT
   #define ENABLE_EVMAP_DEBUG_PASS 
   #define ENABLE_EVMAP_DEBUG */
#define MAPSIZE 65536
#ifdef _MSC_VER
#endif

#ifndef _USE_ISOC99B
#define __func__ "Your_compiler_did_not_support_C99"
#endif

#include <errno.h>
#include <memory.h>
#include <reactor.h>

#ifdef ENABLE_EVMAP_DEBUG
#include <stdio.h>
#include <stdarg.h>
#include <time.h>
#include <malloc.h>
#endif

#define malloc malloc

#ifdef ENABLE_EVMAP_DEBUG

/* Just for testing stuff */

struct event;

typedef void event_cb_t(struct event *, u_int, void *);

struct event {
    long sockfd;
    long prio;
    long mode;
    long signal;
    long happen;
    
    void *arg;
    event_cb_t *cb;
};

/* End -- Just for testing stuff */

#endif

struct evmap_branch;

struct evmap {
    long nr_node;
    long nr_depth;
    struct evmap_branch *tree;
};

struct evmap_branch {
    struct evmap *evmap;
    void **child;
};

#ifdef ENABLE_EVMAP_DEBUG_PASS
static inline int debug_times = 1;
#endif

struct evmap reactor_evmap;

static inline inline void evmap_debug_pass(char *file, char *func, int line)
{
#ifdef ENABLE_EVMAP_DEBUG_PASS
    printf("File: %s\n"
           "Func: %s()\n"
           "Line: %d\n"
           "Pass %d\n\n", file, func, line, debug_times);
    debug_times++;    
#endif
}

static inline inline void evmap_debug_print(char *file, char *func, int line, char *fmt, ...)
{
#ifdef ENABLE_EVMAP_DEBUG_PRINT
    va_list va;
    va_start(va, fmt);
    vprintf(fmt, va);
    va_end(va);
#endif
}

static inline void *zalloc(size_t sz)
{
    void *mem = (void *)malloc(sz);
    return (!mem)?(NULL):(memset(mem, 0, sz));
}

static inline inline struct evmap_branch *evmap_alloc_branch(struct evmap *ctl)
{
    struct evmap_branch *tmp = \
                zalloc(sizeof(struct evmap_branch) + MAPSIZE * sizeof(long));
    if(!tmp) {
        return (long)NULL;
    }
    evmap_debug_pass("stuff_tree.c", __func__, __LINE__);
    tmp->evmap = ctl;
    tmp->child = (void **)((char *)tmp + sizeof(struct evmap_branch));
    return tmp;
}

static inline inline int evmap_grow(struct evmap *ctl)
{
    struct evmap_branch *tmp = evmap_alloc_branch(ctl);

    if(!tmp) {
        return -ENOMEM;
    }
    tmp->child[0] = ctl->tree;
    ctl->tree = tmp;
    ctl->nr_depth++;
    return 0;
}

static inline inline uint64_t evmap_power(uint64_t n, int power)
{
    uint64_t ret = n;

    for(power = power - 1;power > 0;power--)
        ret = ret * n;
    return ret;
}

static inline inline int evmap_find_bucket(struct evmap *ctl, uint64_t nr, int depth)
{
    uint64_t nr64 = nr;
    uint64_t n = evmap_power(ctl->nr_node, depth);

    if(!depth) {
        nr64 %= ctl->nr_node;
        goto out;
    }
    nr64 /= n;
    for(;nr64 >= ctl->nr_node;nr64 /= ctl->nr_node);
out:
    return nr64;
}

static inline inline int evmap_build_path(struct evmap *ctl, 
                uint64_t nr)
{
    struct evmap_branch *branchp = ctl->tree;
    struct evmap_branch *tmpbp;
    long hole;
    long i = ctl->nr_depth - 1;
    int ret = -ENOMEM;

    for(;i;i--) {
        tmpbp = (struct evmap_branch *)branchp->child[hole = evmap_find_bucket(ctl, nr, i)];
        if(!tmpbp) {
            if((tmpbp
                = (struct evmap_branch *)(branchp->child[hole]
                = (void *)evmap_alloc_branch(ctl)))
                == NULL) {
                goto out;
            }
        }
        branchp = tmpbp;
    }
    ret = 0;
out:
    return ret;
}

static inline int __evmap_get(struct evmap *ctl, 
                uint64_t nr, 
                void **output)
{
    struct evmap_branch *branchp = ctl->tree;
    struct evmap_branch *tmpbp;
    long i = ctl->nr_depth - 1;
    int ret = 0;

    for(;i;i--) {
        tmpbp = (struct evmap_branch *)branchp->child[evmap_find_bucket(ctl, nr, i)];
        if(!tmpbp) {
            goto out;
        }
        branchp = tmpbp;
    }
    if(!output) {
		ret = -EINVAL;
        goto out;
    }
    *output = branchp->child[evmap_find_bucket(ctl, nr, 0)];
    evmap_debug_pass("stuff_tree.c", __func__, __LINE__);
    ret = 0;
out:
    return ret;
}

static inline int __evmap_insert(struct evmap *ctl, 
                uint64_t nr, 
                void *input)
{
    struct evmap_branch *branchp = ctl->tree;
    struct evmap_branch *tmpbp;
    long i = ctl->nr_depth - 1;
    int ret = -1;

    if((nr < ctl->nr_node) && (ctl->nr_depth == 1)) {
        branchp->child[(long)nr] = input;
        ret = 0;
        goto out;
    }

    if(nr >= evmap_power((uint64_t)ctl->nr_node, ctl->nr_depth)) {
        if(evmap_grow(ctl) == -1) {
            goto out;
        }
        i = ctl->nr_depth - 1;
        branchp = ctl->tree;
    }
    for(;i;i--) {
retry:
        tmpbp = (struct evmap_branch *)branchp->child[evmap_find_bucket(ctl, nr, i)];
        if(!tmpbp) {
            if((ret = evmap_build_path(ctl, nr)) < 0) {
				goto out;
			}
            goto retry;
        }
        branchp = tmpbp;
    }
    if(!input) {
		ret = -EINVAL;
        goto out;
    }
    branchp->child[evmap_find_bucket(ctl, nr, 0)] = input;
    evmap_debug_pass("stuff_tree.c", __func__, __LINE__);
    ret = 0;
out:
    return ret;
}

static inline void __evmap_delete(struct evmap *ctl, 
                uint64_t nr)
{
    struct evmap_branch *branchp = ctl->tree;
    struct evmap_branch *tmpbp;
    long i = ctl->nr_depth - 1;

    if(nr >= evmap_power((uint64_t)ctl->nr_node, ctl->nr_depth)) {
        if(evmap_grow(ctl) == -1) {
            goto out;
        }
        i = ctl->nr_depth - 1;
        branchp = ctl->tree;
    }
    for(;i;i--) {
        tmpbp = (struct evmap_branch *)branchp->child[evmap_find_bucket(ctl, nr, i)];
		if(!tmpbp) {
            goto out;
        }
        branchp = tmpbp;
    }
    branchp->child[evmap_find_bucket(ctl, nr, 0)] = 0;
    evmap_debug_pass("stuff_tree.c", __func__, __LINE__);
out:
    return;
}

static inline int __evmap_init(struct evmap *ctl)
{
    ctl->nr_node = MAPSIZE;
    ctl->nr_depth = 1;
    ctl->tree = evmap_alloc_branch(ctl);
    if(!ctl->tree) {
        return -ENOMEM;
    }
    return 0;
}

int evmap_init()
{
    return __evmap_init(&reactor_evmap);
}

void evmap_delete(uint64_t nr)
{
	__evmap_delete(&reactor_evmap, nr);
}

int evmap_insert(uint64_t nr, void *input)
{
	return __evmap_insert(&reactor_evmap, nr, input);
}

int evmap_get(uint64_t nr, void **output)
{
	return __evmap_get(&reactor_evmap, nr, output);
}

#ifdef ENABLE_EVMAP_DEBUG

int main()
{
    time_t from, to;
    long i = 0;
    struct event *foo;
    evmap_init();
    from = clock();

    for(i = 0;i < 1000000;i++) {
        foo = (struct event *)zalloc(sizeof(struct event));
        evmap_debug_pass("stuff_tree.c", __func__, __LINE__);

        evmap_insert(i, foo);

        foo->sockfd = i;
        foo = 0;

        evmap_get((uint64_t)i, &foo);
        evmap_debug_print("stuff_tree.c", __func__, __LINE__, "Foo->sockfd: %d\n", foo->sockfd);
    }

    to = clock();
    printf("Finish! Time spending: %lu\n", to - from);

    foo = 0;
    evmap_get((uint64_t)131071, &foo);
    printf("Foo->sockfd: %d\n", foo->sockfd);
	evmap_delete(131071);
	foo = 0;
	evmap_get(131071, &foo);
	if(foo)
		printf("Foo->sockfd: %d\n", foo->sockfd);
    getchar();
}

#endif